//1.滑动窗口 --- 水果成篮
//使用容器:
class Solution {
public:
    int totalFruit(vector<int>& f) {
        unordered_map<int, int> hash;
        int n = f.size();
        int l = 0, r = 0, ret = 0;
        while(r < n)
        {
            hash[f[r]]++; ///进窗口
            while(hash.size() > 2)
            {
                hash[f[l]]--; //出窗口
                if(hash[f[l]] == 0) 
                    hash.erase(f[l]);
                l++;
            }
            ret = max(ret, r - l + 1);
            r++;
        }
        return ret;
    }
};


//数组模拟哈希表:
class Solution {
public:
    int totalFruit(vector<int>& f) {
        int kinds = 0;
        int hash[100001] = {0};
        int n = f.size();
        int l = 0, r = 0, ret = 0;
        while(r < n)
        {
            hash[f[r]]++; ///进窗口
            if(hash[f[r]] == 1) kinds++;
            while(kinds > 2)
            {
                hash[f[l]]--; //出窗口
                if(hash[f[l]] == 0) 
                    kinds--;
                l++;
            }
            ret = max(ret, r - l + 1);
            r++;
        }
        return ret;
    }
};


//2.滑动窗口-找到字符串中所有字母异位词
//解法一: 更新结果时暴力判断两个哈希表是否相等
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = {0}, hash2[26] = {0};
        for(auto x : p) hash1[x - 'a']++;
        int len = p.size();
        int l = 0, r = 0;
        int n = s.size();
        while(r < n)
        {
            char in = s[r];
            hash2[in - 'a']++; //进窗口
            if(r - l + 1 > len) //判断 
            {
                char out = s[l];
                hash2[out - 'a']--; //出窗口
                l++;
            }   
            //判断两个哈希表是否相等
            int flag = 1;
            for(char ch = 'a'; ch <= 'z'; ch++)
            {
                if(hash1[ch-'a'] != hash2[ch-'a'])
                    flag = 0;
            }
            if(flag == 1)
                ret.push_back(l);
            r++;
        }
        return ret;
    }
};


//解法二: 优化两个哈希表的判断
//使用变量count统计窗口内有效字符的个数, 进窗口和出窗口时都维护一下count, 更新结果时只需要判断count和len是否相等即可
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len = p.size();
        int hash1[26] = {0};
        int hash2[26] = {0};
        vector<int> ret;
        for(auto x : p) hash1[x - 'a']++;
        int n = s.size();
        int l = 0, r = 0, count = 0;
        while(r < n)
        {
            char in = s[r];
            hash2[in - 'a']++; //进窗口
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if(r - l + 1 > len) //判断
            {
                int out = s[l];
                if(hash2[out - 'a'] <= hash1[out - 'a']) count--;
                hash2[out - 'a']--;
                l++;
            }
            if(count == len) ret.push_back(l);
            r++;
        }
        return ret;
    }
};